﻿#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996) 
#include <stdio.h>
//上节课的知识回顾：
//
//斐波那契的时间复杂度和空间复杂度计算
//时间复杂度：O(N²)   如果忽略边边角角，其实就是细胞分裂，以2为公比的等比数列，所以我们的基本操作次数的类和就是，
//2的0次方+2的1次方+2的2次方+……+2的N-2次方，总共n-1项，结果就是2的N-1次幂-1，忽略次要因素后，变成2的N次方（渐进渐进渐进表示法）

//切记！不要抠细节！1024=2的10次方

//long long Fib1(int N)//求斐波那契数列中的第n项
//{
//	if (N < 3)
//		return 1;
//
//	return Fib(N - 1) + Fib(N - 2);
//}
//long long Fib2(int N)
//{
//	int a = 1;
//	int b = 1;
//	int ret = 0;
//	for (int i = 0; i < N-2; i++)//优化之后的算法时间复杂度变为O(N)
//	{
//		ret = a + b;
//		a = b;
//		b = ret;
//	}
//	return ret;
//}
//int main()
//{
//	long long a = Fib2(3);
//	printf("%d", a);
//}

//空间复杂度：O(N)   关键点：时间是累积的一去不复返，空间是可以重复利用的。
//就比如我们顺着一条递归线，一直往下调用直到满足递归结束条件，现在我们开辟了n（或n-1）个栈帧，
//然后进行归，开辟的栈帧又会一个一个的销毁。然后我们在顺着另一条递归线进行递归，此时我们每次开辟的栈帧空间是和上一条递归线
//中开辟的空间使用情况是一样的，因为我们的栈帧是可以重复利用的。

//下面用代码来给大家展现一下函数栈帧重复使用的魅力。
//void func1()
//{
//	int a = 0;
//	printf("%p\n", &a);
//}
//void func2()
//{
//	int b = 0;
//	printf("%p\n", &b);//通过运行结果我们可以看出，a的地址和b的地址其实是一样的，由此可见我们的栈帧空间是重复利用滴！
//}
//int main()
//{
//	func1();
//	func2();//时间是累积的一去不复返，空间是可以重复利用的
//
//	return 0;
//}

//具体过程就是，我们先开辟main的栈帧，然后开辟func1的栈帧，在这里面开辟变量a的空间，打印之后，最后销毁这块儿大的函数栈帧空间，
//然后再返回到main的栈帧里面
//然后我们开辟func2的栈帧（大小可能和func1有所不同），在原来开辟变量a空间的地方再开辟我们的变量b空间，打印之后，也是销毁这块儿
//大的函数栈帧空间，再返回到main的栈帧里面

//面试题：旋转数组（力扣）
//力扣报超时的两种原因：1.算法效率低 2.程序出现死循环
//思路一：遍历法
//思路二：额外开辟数组，以空间换时间，再把新数组内容拷贝到原数组。  注意：OJ是支持变长数组的，就是数组里面有变量的写法
//思路三：数组多次翻转


//学到算法这里的时候，我们一定要注意几点
//1.画图。 将思路用图像呈现出来，包括细节的呈现
//2.遇到问题一定要去调试。
//3.别去记代码，要自己去思考，画图，将整个思路呈现出来
//
//一定要提高自己解决问题的能力，通过画图调试这些方法






//一：线性表（正题开始）
//1.1概念：
//线性表（linear list）是n个具有相同特性的数据元素的有限序列。 
//线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
//
//线性表在逻辑上是线性结构，也就说是连续的一条直线。
//但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
//
//二：顺序表
//2.1概念：
//顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
//
//要求：数据必须是连续存储的
//
//数据结构就是我们定义一个结构，这个结构可以是链表，顺序表等等，然后我们去实现多个函数来操控这个结构，对这个结构进行数据的
//增删查改,这样就可以帮助我们在内存中管理我们的数据
//2.2动态顺序表
//由于我们指针是可以维护一块儿空间的，所以我们就可以在顺序表中定义一个指针变量，让这个变量去维护一块儿动态开辟的内存空间



//Oj题目的说明：
//1.接口型：不需要写头文件，主函数等等，提交代码之后会和服务器上准备好的代码合并，再编译运行
//测试用例：通过参数传过来的
//返回结果：一般是通过返回值拿到的，也有可能是输出型参数

//数组相关面试题：
//1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。https://leetcode.cn/problems/remove-element/
//void init(int* ps)
//{
//	int i = 0;
//	for (i = 0; i < 10; i++)
//	{
//		ps[i] = 0;
//	}
//	ps接收数组名，ps此时就是个地址，（根据数组名就是首元素地址，首元素地址就是数组名），我们就可以知道，ps==arr,arr怎么用
//    ps就可以怎么用，arr[]==ps[],*(arr+i)==*(ps+i)
//}
//int main()
//{
//	int arr[10] = { 0 };
//	init(arr);
//}
//思路一：
//int removeElement(int* nums, int numsSize, int val) 
//{
//    int src = 0;
//    int dst = 0;
//    while (src < numsSize)
//    {
//        if (nums[src] != val)
//        {
//            nums[dst] = nums[src];
//            src++;
//            dst++;
//        }
//        else
//            src++;
//    }
//    return dst;
//}
//思路二：这种方法可以优化我们的算法，如果首元素位置上是val的话，我们就省去了保留的元素重复赋值的操作，提升效率
//int removeElement(int* nums, int numsSize, int val)
//{
//    int left = 0, right = numsSize;
//    while (left < right) 
//    {
//        if (nums[left] == val)
//        //即使right指向的是val也没关系，我们的left位置不动，知道right传过来的值不是val我们的left才++
//        {
//            nums[left] = nums[right - 1];
//            right--;
//        }
//        else 
//        {
//            left++;
//        }
//    }
//    return left;
//}

//2. 删除排序数组中的重复项。https://leetcode.cn/problems/remove-duplicates-from-sorted-array/


//值得注意的是：堆溢出的原因一般是数组越界，
//Oj上出现bug时，我们有三种解决方法，
//1.观察力扣的测试用例，进行相应的画图分析，检查程序问题
//2.vs上调试
//3.在力扣上加printf，观察输出结果，力扣会给出stdout的结果

//一：王亚楠自己的方法，啊哈
//int removeDuplicates(int* nums, int numsSize)
//{
//    if (numsSize <= 1)
//        return numsSize;
//
//    int src = 1;
//    int dst = 0;
//    while (src < numsSize)
//    {
//        while (nums[dst] == nums[src])
//        {
//            src++;
//            if (src >= numsSize)
//                //判断是否越界，如果在while循环里面越界，只能说明这个数组全是相同元素
//            {
//                return dst + 1;
//            }
//        }
//        dst++;
//        nums[dst] = nums[src];
//        src++;
//    }
//    return dst + 1;
//}

//二：老师的方法，三指针
//int removeDuplicates(int* nums, int numsSize)
//{
//    int begin = 0;
//    //老师的算法就是用begin和end去遍历一段相同的数，直到两者不相等，然后把begin给到dst，dst+1，需要额外判断的情况就是
//    //当end越界之后，我们有最后一步操作就是，把begin的值给到dst
//
//    int end = 1;
//    int dst = 0;
//    if (numsSize <= 1)
//        return numsSize;
//    while (end < numsSize)
//    {
//        if (nums[begin] == nums[end])
//        {
//            end++;
//        }
//        else
//        {
//            nums[dst] = nums[begin];
//            begin = end;
//            dst++;
//            end++;
//        }
//
//    }
//    //end越界之后，我们还需要，将begin中的数据在赋值给下标是dst的数据当中，这是最后一步
//    nums[dst] = nums[begin];
//    dst++;
//
//    return dst;
//}

//3. 合并两个有序数组。https://leetcode.cn/problems/merge-sorted-array/
//思路一:我们可以重新搞一个tmp数组，我们比较这两个有序数组，哪个元素先小，我们就把哪个元素先放到我们的tmp数组里面
//       当两个有序数组的元素全被遍历完之后，我们的tmp数组就是合并之后的结果了，然后我们在根据题目要求，将合并结果
//       重新拷贝回数组1里面去
//思路二:例如123000 和 256这两个数组如果从前往后比，我们找较小值得话，我们第一个数组里的2会覆盖掉前面数组里的
//       元素3，所以我们考虑从后往前遍历，找出最大值，谁先大，谁就先放到arr1中的最后位置
//       总结一下就是，从前往后放 找小，从后往前放 找大
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int end1 = m - 1, end2 = n - 1;
    int end = m + n - 1;
    while (end1 >= 0 && end2 >= 0)
    {
        if (nums1[end1] > nums2[end2])
        {
            nums1[end--] = nums1[end1--];
            //  end1--;
            //  end--;
        }
        else
        {
            nums1[end--] = nums2[end2--];
            //  end--;
            //  end2--;
        }
    }
    while (end2 >= 0)//如果end2遍历完我们什么也不用干，因为end1中放的就是他自己
    {
        nums1[end--] = nums2[end2--];
        //  end2--;
    }

}
































































